알고리즘 복잡도 분석 (Big-O)

일반적으로 입력의 개수 𝑛과 시간 복잡도 함수 𝑇(𝑛)의 관계는 상당히 복잡할 수 있다. 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 Big-O 표기법이라고 한다. 예를들어 알고리즘이 𝑛에 비례하는 수행시간을 가진다고 말하는 대신 해당 알고리즘의 시간 복잡도가 𝑂(n)이라고 한다. 두 개의 함수 𝑓(𝑛)과 𝑔(𝑛)이 주어졌을 ...

알고리즘시간 복잡도자료구조Big OBig O

프로그램 시간의 복잡도에 관한 작은 문제

오늘 수업 후 문제는 다음과 같은 순서가 있다 책에서 제시한 답안의 복잡도는 O(n)이다. 내 느낌은 O(n2)인 것 같다. 그래서 원문 끝에 31의 디스플레이 출력 문구를 추가하여 검증했다. 여러 번 시도한 후에 답안이 확실히 가까워졌다(n2)/2를 발견했다. 그래서 개인적인 느낌으로 책에 답안이 틀린 것 같다. 가르쳐 달라. 나는 문제가if문장이 실행될 때 확률이 있다는 것을 발견했다. ...

시간 복잡도